Batch 2 - Class 315 - Hat Puzzles

• [Celtic Knots] Can you think about what will happen if we made a torus out of this? i.e. we joined the horizontal ends, and then we also joined the vertical ends?

• Albert and Bilbert are about to play a game in which hats — either red or blue —will be placed on their heads. Each will be able to see the color of his partner’s hat, but not the color of his own. At the blow a whistle Albert and Bilbert will simultaneously make a guess as to the color of his own hat. Incorrect guesses will not be punished. A win consists of at least one correct guess. What strategy can Albert and Bilbert agree upon to secure a win?
• Answer: Albert guesses the same color hat he sees on Bilbert. Bilbert guesses the opposite of what he sees on Albert.
• Following the same rules as question 1, one-hundred players will play the same game with hats that can be any of 100 different colors. (Not all colors need be used.) Each player can see the colors of her 99 colleagues. If a win consists of at least one correct guess and no penalty for incorrect guesses, devise a strategy that guarantees a win.
• Answer: First try with 3 people and 3 hat colors. Then try to generalize. Label the hat colors 0 to 99 and number the players 0 to 99. Have each player sum the colors she sees, working mod 100, and guess the color number that brings this sum up to the number she has been assigned as a player (again working mod 100). If the sum of all hat colors, mod 100, is s, then player s is sure to make a correct guess.
• There are three people standing in a queue so that the last person can see both people in front, the middle person can see one person in front, and the first person can't see anyone. Three hats, chosen out of three red and two blue hats, are placed one each on their head. The last person is asked the color of hat on his head, and he says "I don't know". The middle person is asked the same and he also says "I don't know". The first person is asked the same question, and he says "I know". How?
• Answer: Since the last person says he doesn't know, the front two have at least one red hat (else the blue hats would be exhausted and the last person would know he has a red hat). Given that the front two have at least one red hat, the fact that the second person says he doesn't know means that the first person has a red hat (otherwise the second person would know he has a red hat).

• Now assume that each of the three people can see the other two, and each has a blue or a red hat (there are no limitations on total number of blue or red hats). When the bell rings, each of them must simultaneously state their hat color, or say "pass". If none of them is wrong but at least one is right, all of them win a big prize. "Pass" doesnt not count as either right or wrong. What is the strategy to maximize their   chances of winning?
• Answer: 75% chance. All people act as follows: if they see two hats of the same color on other two people, they state the color opposite in color. If they see different color hats on other two people, they say "pass".

• We are back to three black and two white hats, and every person can see the other two people. At every bell, whoever knows his hat color has to announce it. What will happen, and how quickly will everyone have announced their hat color?
• Answer: 
• If there are two people wearing white hats, on the first bell, the third person will announce that he know color of his hat (black), and on the next bell, the other two, having seen what the third person said, will announce that they have white hats. 
• If there is one person with white hat, and two with black, on the first bell, no one will announce anything. On the next bell, people with black hat (who can see one white hat) will each announce that they have a black hat (otherwise someone would have seen two white hats and announced at first bell). On the third bell, the remaining person will announce the white hat.
• If all three have black hats, no one will announce on first two bells, but all three will realize that everyone must have a black hat at the third bell (otherwise one of the top two scenarios would have happened), and everyone will simultaneously announce on third bell.

• (Khan Academy) 10 prisoners are given a chance of survival by the jailer. The jailer tells them that the next morning, he will have them stand in a queue (so that the last person can see the nine people in front, the second last people can see eight people in front of him, and so on), and then place either a red hat or a purple hat on each person's head. The person hence will be able to see the color of hat for people in front of him (but not his own hat). The jailer will then start from the last person, and ask each person "What is the color of hat on your head". The person can answer "red" or "purple". If the person's answer is correct, he will be released, else he will be killed. The jailer will then ask the same question to the second last person, and so on. The prisoners have the night to figure out the strategy so that maximum number of prisoners can survive (on a guaranteed basis). Figure out a strategy to save the maximum number of prisoners.
• Answer: "Last guy calls the odd number of hats in front". Every person there on keeps a count of odd or even parity.